// hdu3480
// 题意：给定n(<=10000)个数，要将其划分成m(<=5000)部分，每一部分的代价
//       是这个部分最大值减去最小值差的平方。问最小代价。
//
// 题解：排序后，很容易得到一个这样的dp，f[i][j]表示前i个，分了j组的代价，
//       转移很明显：
//         f[i][j]=min(f[k][j-1] + (a[i] - a[k + 1])^2), 0<=k<i
//       右边那个函数是满足四边形不等式的，然后应该可以证明（打印观察），
//       f也是满足的。
//         f[i][j]=min(f[k][j-1] + (a[i] - a[k + 1])^2)
//          (s[i-1][j] <= k <= s[i][j+1])
//         其中s[i][j]表示f[i][j]从最小的最优状态转移过来。
//       但是直接这么做要用二维来存状态，也不方便滚存，会MLE。
//       所以我们把j作为第一维，i作为第二维，然后方程的转移改为
//          (s[i][j-1] <= k <= s[i+1][j])
//       这样j这维就可以状压了，然后可以使用long long就不会MLE。
//
// run: $exec < input
#include <iostream>
#include <cstring>
#include <algorithm>

long long const  inf = (1ll) << 44;
int const maxn = 10007;
int const maxm = 5007;
long long f[maxn][2];
short s[maxn][maxm];
int a[maxn];
int n, m;

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case " << ti << ": ";
		std::cin >> n >> m;
		for (int i = 1; i <= n; i++) std::cin >> a[i];
		std::sort(a + 1, a + n + 1);

		for (int i = 0; i <= n; i++) {
			f[i][0] = f[i][1] = inf;
			for (int j = 0; j <= m; j++) s[i][j] = 0;
		}

		/*
		f[0][0] = 0;
		for (int i = 1; i <= n; i++) {
			int t = std::min(i, m);
			s[i][t + 1] = t;
			for (int j = t; j >= 1; j--) {
				for (int k = s[i - 1][j]; k <= s[i][j + 1]; k++) {
					int tmp = (a[i] - a[k + 1]) * (a[i] - a[k + 1]);
					if (f[k][j - 1] + tmp < f[i][j]) {
						f[i][j] = f[k][j - 1] + tmp;
						s[i][j] = k;
					}
				}
			}
		}
		*/
		f[0][0] = 0;
		int now = 0, prev = 0;
		for (int j = 1; j <= m; j++) {
			s[n + 1][j] = n;
			prev = now; now ^= 1;
			for (int i = n; i >= j; i--) {
				f[i][now] = inf;
				for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++) {
					long long tmp = a[i] - a[k + 1];
					tmp *= tmp;
					if (f[k][prev] + tmp < f[i][now]) {
						f[i][now] = f[k][prev] + tmp;
						s[i][j] = k;
					}
				}
			}
		}
		std::cout << f[n][now] << '\n';
	}
}

